Computers utilize a wide variety of disks as storage media for user data. Disk technologies currently provide optical disks, magnetic disks, hard disks, floppy disks, and removable disks, and new disk technologies are being actively researched and developed. Indeed, some disks used by computers in the future may be cubical or some other shape rather than flat and circular.
FIG. 1 illustrates a disk 100 attached to a disk drive 102. The disk 100 illustrates physical characteristics of both floppies and hard disks; flash memory, cubical disks or other disks may appear in different configurations than the one shown here. The disk 100 contains a number of concentric data cylinders such as the cylinder 104. The cylinder 104 contains several data sectors, including sectors 106 and 108. The sectors 106 and 108 are located on an upper side 110 of the disk 100; additional sectors may be located on a lower side 112 of the disk 100. The sides 110, 112 of the disk 100 define a platter 114. A hard disk may contain several platters. The upper side 110 of the disk 100 is accessed by a head 116 mounted on an arm 118 secured to the drive 102. Optical or cubical disks may be accessed by other means, such as photoemitters or photoreceptors, and flash memory or other memory disks are accessed by electronic circuits familiar to those of skill in the art.
A given sector on the disk 100 may be identified by specifying a head, a cylinder, and a sector within the cylinder. A triplet specifying the head number, cylinder number, and sector number in this manner is known as a "physical sector address." Alternatively, a given sector may be identified by a logical sector address, which is a single number rather than a triplet of numbers.
Many disks mold the available space into one or more partitions by using a partition table located on the disk. A wide variety of partitions are used, and more partition types will no doubt be defined over time. Many partitions reside on a single disk, but some use volume sets, stripe sets, mirror sets, or other approaches to store a single partition's data on more than one disk. A partial list of current partitions and their associated file systems is given in U.S. patent application Ser. No. 08/834,004, filed Apr. 12, 1997, and incorporated here by reference. The list includes a variety of 12-bit, 16-bit, and 32-bit FAT file systems and numerous other file systems.
A file system of particular interest here is the NT File System ("NTFS"). Discussions of NTFS are provided in "Inside the Windows NT File System", by Helen Custer, ISBN 1-55615-660-X, as well as in marketing and technical materials available in hard copy and on the Internet from Microsoft Corporation and other sources. Those of skill in the art will note that these discussions sometimes involve unimplemented specifications or mere speculations.
NTFS contains advanced file system features which make it more complex or difficult to manipulate NTFS partitions than it is to manipulate partitions organized by many existing FAT file systems. More precisely, NTFS combines features such as the use of a database paradigm to support indexing of file attributes; multiple data streams per file; blurring of the distinction between system and user areas; recoverability by use of a log; recoverability by use of transactions; support for large disks; security descriptors constraining access to file objects; Unicode names; support for POSIX features such as links; bad cluster remapping; caching support; virtual memory support; system structure compression; balanced tree directory structures; support for volume spanning, volume sets, stripe sets, mirror sets, and other features which divide a file system's contents between disks or partitions; and/or a relocatable system area. "Attributes" are also known as "data streams"; some advanced file systems allow a single file to hold multiple data streams.
One partition table composition, denoted herein as the "IBM-compatible" partition table, is found on the disks used in many IBM.RTM. personal computers and IBM-compatible computers (IBM is a registered trademark of International Business Machines Corporation). IBM-compatible partition tables may be used on a wide variety of disks, with a variety of partition and file system types, in a variety of ways. In particular, the partition table format may be changed without necessarily changing file system formats, and vice versa.
As shown in FIG. 2, one version of an IBM-compatible partition table 200 includes an Initial Program Loader ("IPL") identifier 202, four primary partition identifiers 204, and a boot identifier 206. As shown in FIG. 3, each partition identifier 204 includes a boot indicator 300 to indicate whether the partition in question is bootable. At most one of the partitions in the set of partitions defined by the partition table 200 is bootable at any given time but "boot management" tools are commercially available to facilitate booting from different partitions.
Each partition identifier 204 also includes a starting address 302, which is the physical sector address of the first sector in the partition in question, and an ending address 304, which is the physical sector address of the last sector in the partition. A sector count 306 holds the total number of disk sectors in the partition. A boot sector address 308 holds the logical sector address corresponding to the physical starting address 302. Additional partition information may be stored in a disk administrator utility or other location outside the partition table, or in an enhanced partition table, particularly when partitions are allowed to span disks.
Some IBM-compatible computer systems allow "logical partitions" as well as the primary partitions just described. All logical partitions are contained within one primary partition; a primary partition which contains logical partitions is also known as an "extended partition."
Each partition identifier 204 also includes a system indicator 310. The system indicator 310 identifies the type of file system contained in the partition, which in turn defines the physical arrangement of data that is stored in the partition on the disk 100 (FIG. 1). For instance, the system indicator may indicate that data is organized in the partition according to some version of NTFS, with multiple data streams, a relocatable system area, and other features noted above. System indicator values not recognized by a particular operating system are treated as designating an unknown file system. The file system associated with a specific partition of the disk 100 determines the format in which data is stored in the partition, namely, the physical arrangement of user data and of file system structures in the portion of the disk 100 that is delimited by the starting address 302 and the ending address 304 of the partition in question. At any given time, each partition thus contains at most one type of file system.
An operating system manages access, not only to the disk 100, but to other computer resources as well. Resources typically managed by the operating system include one or more disks and disk drives, memory (RAM and/or ROM), micro-processors, and I/O devices such as a keyboard, mouse, screen, printer, tape drive, modem, serial port, parallel port, or network port.
It is sometimes desirable to alter the contents of a partition in-place without copying all necessary user and system data off the disk to a temporary storage location such as a tape or another disk and using FDISK or a similar tool. Inventions for in-place partition manipulation without destroying user data are described in U.S. Pat. Nos. 5,675,769 and 5,706,472, and in patent applications Ser. No. 08/932,530 and Ser. No. 08/834,004 (incorporated herein by reference). Software embodying the patented inventions is commercially available from PowerQuest Corporation of Orem, Utah.
However, the aforementioned patents do not teach comprehensive methods for canonizing NTFS partitions, that is, for relocating system files and other data to place them at or near predetermined positions within the partition. In addition, although the aforementioned patents provide useful methods for reclaiming storage space by changing cluster size and/or partition size, the patents do not present certain other methods for optimizing NTFS storage efficiency.
Thus, it would be an advancement in the art to provide an improved system and method for manipulating advanced file system partitions, such as NTFS partitions, in-place without destroying user data.
Such a system and method are disclosed and claimed herein.